package com.example.demo.leetcode;

/**
 * 链接：<a href="https://leetcode.cn/problems/rotate-image/?envType=study-plan-v2&envId=top-interview-150">https://leetcode.cn/problems/rotate-image/?envType=study-plan-v2&envId=top-interview-150</a><br>
 * <p>
 * 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。<br>
 * <p>
 * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。<br>
 * <p>
 * <p>
 * 提示：
 * <p>
 * n == matrix.length == matrix[i].length<br>
 * 1 <= n <= 20<br>
 * -1000 <= matrix[i][j] <= 1000<br>
 */
public class _48_旋转图像 {

    public static class Solution {

        /**
         * 官方题解-方法一：使用辅助数组 <br>
         * 矩阵旋转90度之后，得到的规律是matrix[row][col] = matrix[col][n-row-1]<br>
         * 这样以来，我们就可以使用一个与matrix大小相同的assist辅助数组，临时存储旋转后的结果。<br>
         * 遍历matrix中的每一个元素，根据上述规则将该元素存储到新的辅助数组中。<br>
         * 在遍历完成之后，再将matrix的引用指向辅助数组<br>
         *
         * <p>
         * 时间复杂度为O(n*n)<br>
         * 空间复杂度为O(n)
         */
        public void rotate(int[][] matrix) {
            int n = matrix.length;
            int[][] assist = new int[n][n];
            for (int row = 0; row < n; row++) {
                for (int col = 0; col < n; col++) {
                    assist[col][n - row - 1] = matrix[row][col];
                }
            }
            matrix = assist;
        }

        /**
         * 官方题解-方法二：原地旋转 <br>
         * <p>
         * 题目中要求我们尝试在不使用额外内存空间的情况下进行矩阵的旋转，也就是说，我们需要「原地旋转」这个矩阵。那么我们如何在方法一的基础上完成原地旋转呢？<br>
         * 我们观察方法一中的关键等式：matrix[row][col] = matrix[col][n-row-1]<br>
         * 它阻止我们进行原地旋转，因为如果我们直接将matrix[row][col]放到原矩阵中的目标位置matrix[col][n-row-1]<br>
         * 则原矩阵中的matrix[col][n-row-1]就被覆盖了。这并不是我们想要的结果。<br>
         * 因为我们可以考虑用一个临时变量temp来暂时存储matrix[col][n-row-1]的值，这样matrix[col][n-row-1]被覆盖了，我们还是可以通过temp获取它原来的值。<br>
         * <p>
         * > temp = matrix[col][n-row-1]<br>
         * > matrix[col][n-row-1] = matrix[row][col]<br>
         * <p>
         * <p>
         * 那么 matrix[col][n−row−1]经过旋转操作之后会到哪个位置呢？我们还是使用方法一中的关键等式，不过这次，我们需要将<br>
         * > row -> col<br>
         * > col -> n-row-1<br>
         * 带入关键等式，就可以得到：<br>
         * matrix[n−row−1][n−col−1]=matrix[col][n−row−1]<br>
         * 同样地，直接赋值会覆盖掉 matrix[n−row−1][n−col−1] 原来的值，因此我们还是需要使用一个临时变量进行存储，不过这次，我们可以直接使用之前的临时变量 temp：<br>
         * <p>
         * > temp = matrix[n−row−1][n−col−1]<br>
         * > matrix[n−row−1][n−col−1] = mat[col][n-row-1]<br>
         * > matrix[col][n-row-1] = matrix[row][col]<br>
         * <p>
         * <p>
         * 我们再重复一次之前的操作，matrix[n−row−1][n−col−1]经过旋转操作之后会到哪个位置呢？<br>
         * matrix[n−col−1][row]=matrix[n−row−1][n−col−1]<br>
         * <p>
         * > temp = matrix[n−col−1][row]<br>
         * > matrix[n−col−1][row] = matrix[n−row−1][n−col−1]<br>
         * > matrix[n−row−1][n−col−1] = mat[col][n-row-1]<br>
         * > matrix[col][n-row-1] = matrix[row][col]<br>
         * <p>
         * <p>
         * 不要灰心，再来一次！matrix[n−col−1][row]经过旋转操作之后回到哪个位置呢？<br>
         * matrix[row][col]=matrix[n−col−1][row]<br>
         * 我们回到了最初的起点 matrix[row][col]<br>
         * <p></p>
         * 这四项处于一个循环中，并且每一项旋转后的位置就是下一项所在的位置！因此我们可以使用一个临时变量 temp 完成这四项的原地交换：
         * > temp = matrix[row][col]<br>
         * > matrix[row][col] = matrix[n-col-1][row]<br>
         * > matrix[n-col-1][row] = matrix[n-row-1][n-col-1]<br>
         * > matrix[col][n-row-1] = tem<br>
         * <p>
         * <p>
         * 当我们知道了如何原地旋转矩阵之后，还有一个重要的问题在于：我们应该枚举哪些位置 (row,col)进行上述的原地交换操作呢？由于每一次原地交换四个位置，因此：<br>
         * 当 n 为偶数时，我们需要枚举 n^2/4=(n/2)×(n/2)个位置，可以将该图形分为四块。保证了不重复、不遗漏；<br>
         * 当 n 为奇数时，由于中心的位置经过旋转后位置不变，我们需要枚举 (n^2−1)/4=((n−1)/2)×((n+1)/2)个位置，需要换一种划分的方式，同样保证了不重复、不遗漏，矩阵正中央的点无需旋转。<br>
         * <p>
         * <p>
         * 时间复杂度为O(n*n)
         * 空间复杂度为O(1),为原地旋转。
         */
        public void rotate2(int[][] matrix) {
            int n = matrix.length;
            //TODO
            //这里需要遍历的点和上面所说的还是你有出入，我不太明白。
            for (int i = 0; i < n / 2; ++i) {
                for (int j = 0; j < (n + 1) / 2; ++j) {
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[n - j - 1][i];
                    matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                    matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                    matrix[j][n - i - 1] = temp;
                }
            }
        }

        /**
         * 官方题解-方法三：用翻转代替旋转 <br>
         * 我们还可以另辟蹊径，用翻转操作代替旋转操作。我们用下面的例子举例：<br>
         * |5  1  9  11 |<br>
         * |2  4  8  10 |<br>
         * |13 3  6  7  |<br>
         * |15 14 12 16 |<br>
         * <p>
         * 先将其通过水平轴翻转得到：<br>
         * |15 14 12 16|<br>
         * |13 3  6  7 |<br>
         * |2  4  8  10|<br>
         * |5  1  9  11|<br>
         * <p>
         * 在根据主对角线反转：<br>
         * |15 13 2  5 |<br>
         * |14 3  4  1 |<br>
         * |12 6  8  9 |<br>
         * |16 7  10 11|<br>
         * <p>
         * 就得到了答案。这是为什么呢？对于水平轴翻转而言，我们只需要枚举矩阵上半部分的元素，和下半部分的元素进行交换，即<br>
         * matrix[row][col] ==> matrix[n−row−1][col]<br>
         * <p>
         * 对于主对角线翻转而言，我们只需要枚举对角线左侧的元素，和右侧的元素进行交换，即<br>
         * matrix[row][col] ==> matrix[col][row]<br>
         * <p>
         * <p>
         * 时间复杂度：O(N^2)，其中 N 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。<br>
         * <p>
         * 空间复杂度：O(1)。为原地翻转得到的原地旋转。<br>
         */
        public void rotate3(int[][] matrix) {
            int n = matrix.length;
            // 水平翻转
            for (int i = 0; i < n / 2; ++i) {
                for (int j = 0; j < n; ++j) {
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[n - i - 1][j];
                    matrix[n - i - 1][j] = temp;
                }
            }
            // 主对角线翻转
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < i; ++j) {
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = temp;
                }
            }
        }
    }
}
